package 双指针系列;

import sun.plugin.javascript.navig.LinkArray;

import java.util.*;
import java.util.Arrays;
import java.util.Collections;

public class ReverseWords {
    //解法一：正则表达式
    public String reverseWords(String s) {
        s = s.trim();   //去除开头和结尾的空格
        String[] a = s.split("\\s+");   //分割空格，得到字符串数组
        List<String> wordList = Arrays.asList(a);//转换为List类型,这里主要为了等会儿可以直接翻转
        // Collection 是一个 集合框架的父接口
        // Collections 是一个包装类。它包含有各种有关集合操作的 静态多态方法。此类 不能实例化，就像一 个工具类，服务于Java的Collection框架。
        /**
         * 1.Shuffle（element）：洗牌方法，将当前集合内的数据进行随机排序。
         * 2.Reverse（element）：逆序排序，对当前集合的元素按照相反的顺序进行排序
         * 3.Sort（element）：对当前集合进行升序排序,实现Comparable接口的类，只能使用一种排序方案，这种方案叫作“自然比较”方案。
         * 原文链接：https://blog.csdn.net/u013317172/article/details/82263256
         */
        Collections.reverse(wordList);//翻转List
        return String.join(" ",wordList);//用空格连接单词成为一个字符串
    }

    //解法二：双指针法
    public String reverseWords1(String s) {
        StringBuilder sb = removeSpace(s);  //去除空格
        reverseString(sb,0,sb.length()-1);
        reverseEachWord(sb);
        return new String(sb);
    }

    public StringBuilder removeSpace(String s){
        //去空格
        s = s.trim();
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(i>0&&c==' '&&s.charAt(i-1)==c){
                continue;
            }
            sb.append(c);
        }
        return sb;
    }


    public void reverseString(StringBuilder sb, int start, int end) {
        /**
         * 反转字符串指定区间[start, end]的字符
         */
        while(start<end){
            char temp = sb.charAt(start);
            sb.setCharAt(start,sb.charAt(end));
            sb.setCharAt(end,temp);
            start++;
            end--;
        }
        //也可以使用
//        sb.reverse();

    }

    private void reverseEachWord(StringBuilder sb) {
        //翻转每个单词
        int left = 0;
        int right = 1;
        int n = sb.length();
        while(left<n){
            while(right<n&&sb.charAt(right)!=' '){
                right++;
            }
            reverseString(sb,left,right-1);
            left = right+1;
            right= left+1;
        }

    }
    class Solution {
        public String reverseWords(String s) {
            int left = 0, right = s.length() - 1;
            // 去掉字符串开头的空白字符
            while (left <= right && s.charAt(left) == ' ') {
                ++left;
            }

            // 去掉字符串末尾的空白字符
            while (left <= right && s.charAt(right) == ' ') {
                --right;
            }

            Deque<String> d = new ArrayDeque<String>();
            StringBuilder word = new StringBuilder();

            while (left <= right) {
                char c = s.charAt(left);
                if ((word.length() != 0) && (c == ' ')) {
                    // 将单词 push 到队列的头部
                    d.offerFirst(word.toString());
                    word.setLength(0);
                } else if (c != ' ') {
                    word.append(c);
                }
                ++left;
            }
            d.offerFirst(word.toString());

            return String.join(" ", d);
        }
    }


}
